import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-26
 * Time: 21:09
 */
public class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> choose = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(startGene);
        choose.add(startGene);
        int count = 1;
        while (!queue.isEmpty()){
            int size = queue.size();
            // 一层一层的往队列里面添加
            for (int i = 0; i < size; i++) {
                String str = queue.poll();
                for (String s : bank) {
                    // 每个字符串都将它可能转化的字符串添加到队列中, 类似于多叉树
                    if (canChoose(str, s) && !choose.contains(s)) {
                        // 如果两个字符串只差一个字符并且没有选过, 那么就使用它
                        if(s.equals(endGene)){
                            // 找到结果直接返回
                            return count;
                        }
                        queue.add(s);
                        choose.add(s);
                    }
                }
            }
            count++;
        }
        return -1;
    }


    /**
     *  判断是不是两个字符串是不是只差一个字符
     * @param s1
     * @param s2
     * @return
     */
    private boolean canChoose(String s1, String s2) {
        if(s1.length() != s2.length()){
            return false;
        }
        int count = 0;
        for (int i = 0; i < s1.length(); i++) {
            if(s1.charAt(i) != s2.charAt(i)){
                count++;
                if(count == 2){
                    return false;
                }
            }
        }
        return true;
    }
}
